/*
 * @Author: szx
 * @Date: 2022-03-15 15:38:17
 * @LastEditTime: 2022-03-15 15:52:02
 * @Description:
 * @FilePath: \leetcode\300-399\332\332_2.js
 */
/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function (tickets) {
    let result = ['JFK'];
    let map = new Map();

    for (const [from, to] of tickets) {
        if (!map.has(from)) {
            map.set(from, []);
        }
        map.get(from).push(to);
    }
    for (const city of map.values()) {
        // 对到达城市列表排序
        city.sort();
    }
    const backtracing = () => {
        if (result.length === tickets.length + 1) {
            return true;
        }
        const lastCityTickets = map.get(result[result.length - 1]);

        if (!lastCityTickets || !lastCityTickets.length) {
            return false;
        }
        for (let i = 0; i < lastCityTickets.length; i++) {
            let city = lastCityTickets[i];
            // 删除已走过航线，防止死循环
            lastCityTickets.shift();
            result.push(city);
            if (backtracing()) {
                return true;
            }
            result.pop();
            lastCityTickets.unshift(city);
        }
    };
    backtracing();
    return result;
};
